import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description: 牛客网: BM77 最长的括号子串
 * <a href="https://www.nowcoder.com/practice/45fd68024a4c4e97a8d6c45fc61dc6ad?tpId=295&tqId=715&ru=/exam/company&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Fcompany">...</a>
 * User: DELL
 * Date: 2023-06-25
 * Time: 22:22
 */
public class Solution {
    /**
     * 解题思路: (动态规划)
     * 状态定义: F(i) = 以第 i 个字符为结尾的最长合格括号子串的长度
     * 状态转移: 当第 i 个字符为 ( 时:
     *              F(i) = 0
     *          当第 i 个字符为 ) 时:
     *              从第 i 个字符开始,往前遍历,当寻找到第 j 到第 i 字符的字串
     *              为合格的括号子串时, F(i) = i-j+1 + F(j-1)
     * 初始化: F(0) = 0  F(1) = 0
     * 返回值: 遍历返回最大值即可
     *
     * 这种解法下,当出现较多连续的右括号的时候,就会变成O(N^2)的时间复杂度,因此需要改进
     * @param s
     * @return
     */
    public int longestValidParentheses (String s) {
        //判空处理
        if (s == null || s.length() == 0) {
            return 0;
        }
        //定义dp数组
        int[] dp = new int[s.length()+1];
        //默认为0,因此不需要初始化
        //状态转移
        for (int i = 1; i <= s.length(); i++) {
            if (s.charAt(i-1) == ')') {
                // 这里使用flag记录右括号的净数量即遇到一个左括号就将
                // flag--,遇见左括号就将flag++,当flag==0时,即为合
                // 格括号子串
                int flag = 1;
                int j = i-1;
                while (j != 0) {
                    if (s.charAt(j-1) == '(') {
                        flag--;
                    } else {
                        flag++;
                    }
                    if (flag == 0) {
                        dp[i] = i-j+1 + dp[j-1];
                        break;
                    }
                    j--;
                }
            }
            //当为左括号时,不需要操作,默认为0
        }
        //遍历返回最大长度
        int max = dp[0];
        for (int i = 1; i <= s.length(); i++) {
            max = Math.max(dp[i],max);
        }
        return max;
    }

    /**
     * 解法二: (动态规划改进)
     * 状态定义: F(i) = 以第 i 个字符为结尾的最长合格括号子串的长度
     * 状态转移: 当第 i 个字符为 ( 时:
     *              F(i) = 0
     *          当第 i 个字符为 ) 时:
     *              1)当第i-1个字符为 ( 时: F(i) = F(i-2) + 2
     *              2)当第i-1个字符为 ) 时:
     *              这种情况下我们利用F(i-1)的值来进行求解.即若F(i-1) = n,
     *              则第i-n-1个字符若为 (,则F(i) = F(i-n-2)+F(i-1)+2,
     *              否则F(i) = 0
     *              这种情况下的解释为:
     *              与该右括号匹配的左括号不在自己旁边，而是它前一个合法序列之前，
     *              因此通过下标减去它前一个的合法序列长度即可得到最前面匹配的左括号
     * 初始化: F(0) = 0  F(1) = 0
     * 返回值: 遍历返回最大值即可
     * @param s
     * @return
     */
    public int longestValidParentheses2 (String s) {
        //判空处理
        if (s == null || s.length() == 0) {
            return 0;
        }
        //定义dp数组
        int[] dp = new int[s.length()+1];
        //默认为0,因此不需要初始化
        //状态转移
        for (int i = 2; i <= s.length(); i++) {
            if (s.charAt(i-1) == ')') {
                if (s.charAt(i-2) == '(') {
                    dp[i] = dp[i-2] + 2;
                } else {
                    if (i-dp[i-1]-1 > 0 && s.charAt(i-dp[i-1]-1-1) == '(') {
                        dp[i] = dp[i-dp[i-1]-2] + dp[i-1] + 2;
                    }
                }
            }
            //当为左括号时,不需要操作,默认为0
        }
        //遍历返回最大长度
        int max = dp[0];
        for (int i = 1; i <= s.length(); i++) {
            max = Math.max(dp[i],max);
        }
        return max;
    }

    /**
     * 解法三: (栈)
     * 总体就是利用栈先进后出的特性,按顺序记录下多余的左括号的下标,之后遇见右括号就弹出
     * 左括号,再计算维护最长子串长度,同时对于右括号多,即遇见右括号时,栈为空的情况,利用
     * 一个start标记,记录下连续括号结束的位置,即后续计算的起始位置.方便维护.
     * @param s
     * @return
     */
    public int longestValidParentheses3 (String s) {
        int res = 0;
        //记录上一次连续括号结束的位置
        int start = -1;
        Stack<Integer> st = new Stack<Integer>();
        for(int i = 0; i < s.length(); i++){
            //左括号入栈
            if(s.charAt(i) == '(')
                st.push(i);
                //右括号
            else{
                //如果右括号时栈为空，不合法，设置为结束位置
                if(st.isEmpty())
                    start = i;
                else{
                    //弹出左括号
                    st.pop();
                    //栈中还有左括号，说明右括号不够，减去栈顶位置就是长度
                    if(!st.empty())
                        res = Math.max(res, i - st.peek());
                        //栈中没有括号，说明左右括号刚好，减去上一次结束的位置就是长度
                    else
                        res = Math.max(res, i - start);
                }
            }
        }
        return res;
    }
}